In communication systems a network node (or so called host) can allocate its ID or address statically or dynamically. In a static configuration, users need to acquire an available address in advance and manually configure the address. In contrast, in a flexible multi-hop environment, such as the type described in IEEE 802.16j, it is not reasonable for operators or users to perform manual configuration. Another choice, dynamic configuration, allows a node to configure its ID or acquire an ID from a centralized server dynamically. In a typical dynamic configuration scheme, all node IDs are assigned randomly, and additional routing algorithms or routing tables are required in order for nodes to exchange or maintain additional routing information and to decide routing paths.
FIG. 1 illustrates an exemplary multi-hop relay (MR) network 100. In network 100, a multi-hop relay base station BS (MR-BS) 102 acts as a root node, and relay stations (RSs) and mobile stations (MSs) act as intermediate nodes or leaf nodes. A network setup process assigns each network node an identification (or address) and constructs routing groups between nodes. For example, RS3 104 is assigned an address and is responsible for forwarding packets from MR-BS destined to RS4 106, and RS1 108 will drop the packets it receives from MR-BS that are destined to RS3. Such routing information may be maintained in a routing table of each RS so that when an intermediate node leaves or enters the network, that newest routing information can be updated.
Two examples show utilization of routing tables. U.S. Pat. No. 6,192,051 discloses a multi-level tree data structure in a centralized routing table and in distributed forwarding tables for forwarding network packets. Each level of each structure is associated with a different field of a network address appearing in received packets. U.S. Pat. No. 6,934,252 discloses binary network address lookups using parent node information stored in routing table entries. Variable length prefixes are stored in a network address forwarding table. Each prefix corresponds to an entry in the forwarding table. Each entry in the forwarding table includes path information regarding parent nodes of each entry in the binary tree.
Node identification may be performed without maintaining a routing table. U.S. Pat. No. 6,618,755 discloses a software facility for automatically identifying subnets in a network by a range of addresses within the network represented by nodes in the network. The addresses each include an ordered series of a fixed number of bits.
A prime factorization method to represent nodes of a network and groups between nodes is described in US2006/0198320, as well as in IEEE C802.16j-06/171. In the forwarding process of this method, a receiving node needs to factorize the ID number of the packet received to determine where to forward the packet. Another method is described in IEEE C802.16j-07/048r6, which relates to a contiguous integer block routing method, in which a network node identifies the integer block of a received address to determine where to forward the packet or if it should drop the packet.